package util;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Tree {
    // 数据源（一位数组，默认：满二叉树、数组对应二叉树为，从上往下，每层从左往右）(无值的孩子，可以用0代替，数组转换为节点时，赋值为空)
    private static int[] treeArray = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; //74	87	98	82	71	75	90	84	58	93
    // private static int[] treeArray = { 74,	87	,98	,82,	71,	75,	90,	84	,58,	93};
    // 内部类：数的节点
    public static class TreeNode{
        int value;
        int Depth;
        TreeNode leftChild;
        TreeNode rightChild;
        TreeNode(int newValue) {
            leftChild = null;
            rightChild = null;
            value = newValue;
        }
    }
    /**
     * 法1 和 法2原理相同，仅仅把数组的值，转化为节点时，保存的方式不同。
     * 原理：利用 满二叉树 的性质。
     *      下标来看：父节点：i，左孩子：2*i，右孩子：2*i+1  （下标从 1 开始）
     *      父节点个数：节点个数/2，向下取整，即为父节点个数
     *      注意：除最后一个父节点外，其余父节点都有两个孩子。最后一个父节点，必有左孩子，可能没有右孩子（单独处理）
     * @param treeArray
     */
// 法1：利用ArraryList<TreeNode>，构造一棵二叉树（注意 ArrayList 的性质）
    // 构造 满二叉树
    public static TreeNode createBinTreeList(int[] treeArray) {
        int length = treeArray.length;
        int lastParentIndex = length/2 -1;
        List<TreeNode> treeNodeList = new ArrayList();
        for (int index = 0; index < length; index++) {
            treeNodeList.add(new TreeNode(treeArray[index])); // 添加在列表末尾
        }
        for (int parentIndex = 0; parentIndex < lastParentIndex; parentIndex++) { // 所有的下标操作，都减去 1
            treeNodeList.get(parentIndex).leftChild = treeNodeList.get(parentIndex*2+1);
            treeNodeList.get(parentIndex).rightChild = treeNodeList.get(parentIndex*2+2);
        }
        treeNodeList.get(lastParentIndex).leftChild = treeNodeList.get(lastParentIndex*2+1);
        if (treeArray.length%2 == 1)
            treeNodeList.get(lastParentIndex).rightChild = treeNodeList.get(lastParentIndex*2+2);
        return treeNodeList.get(0);
        /**  数组：利用TreeNode[]类型的数组，构造一棵二叉树（注意 数组 的性质）
        * public static TreeNode createBinTreeArray(int[] treeArray) {
        *    int length = treeArray.length;
        *    int lastParentIndex = length/2 -1;
        *    TreeNode[] treeNodeArrary = new TreeNode[length];
        *    for (int index = 0; index < treeArray.length; index++) {
        *        treeNodeArrary[index] = new TreeNode(treeArray[index]);
        *    }
        *    for (int parentIndex = 0; parentIndex < lastParentIndex; parentIndex++) { // 所有的下标操作，都减去 1
        *        treeNodeArrary[parentIndex].leftChild = treeNodeArrary[parentIndex*2+1];
        *        treeNodeArrary[parentIndex].rightChild = treeNodeArrary[parentIndex*2+2];
        *    }
        *    treeNodeArrary[lastParentIndex].leftChild = treeNodeArrary[lastParentIndex*2+1];
        *    if (treeArray.length%2 == 1)
        *        treeNodeArrary[lastParentIndex].rightChild = treeNodeArrary[lastParentIndex*2+2];
        *    TreeNode root = treeNodeArrary[0];
        *    return root;
        * }
        */
    }
    /**
     * 先序遍历 （根，左，右）
     * @param treeNode 遍历的节点
     */
    public static void preOrderTraverse(TreeNode treeNode) {
        if (treeNode == null)
            return;
        System.out.print(treeNode.value + "\t");
        preOrderTraverse(treeNode.leftChild);
        preOrderTraverse(treeNode.rightChild);
    }
    /**
     * 层次遍历(满二叉树)
     * 维护一个队列，先在队列中增加根结点，维护两个指针，一个前端，一个后端）<p>
     * 之后对于随意一个结点来说。在其出队列的时候（前指针移动），访问之。同一时候假设左孩子和右孩子有不为空的，入队列<p>
     * @param treeNode 遍历的节点
     */
    public static void levelOrder(TreeNode treeNode) {
        if (treeNode == null)
            return;
        int length = treeArray.length;
        TreeNode[] queue = new TreeNode[length];  // 构造一个数组队列（保存层次遍历结果）
        int prePoint = 0; // 当前访问的父节点
        int latPoint = 0; // 当前访问的尾节点
        queue[0] = treeNode;      // 初始化构造root根节点,维护两个指针
        while (prePoint <length){
            System.out.print(queue[prePoint].value+"\t");
            if(queue[prePoint].leftChild != null)
                queue[++latPoint] = queue[prePoint].leftChild;
            if(queue[prePoint].rightChild != null)
                queue[++latPoint] = queue[prePoint].rightChild;

            prePoint++;

        }
    }
    public static void main(String[] args) {
        System.out.print("先序遍历：");
        TreeNode root1 = createBinTreeList(treeArray);
        preOrderTraverse(root1);
        System.out.println();
        System.out.print("层次遍历：");
        TreeNode root = createBinTreeList(treeArray);
        levelOrder(root);
    }



}
